<?php
// This file is part of Preg question type - https://code.google.com/p/oasychev-moodle-plugins/
//
// Preg question type is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <http://www.gnu.org/licenses/>.

/**
 * Defines generic node classes, generated by parser. These nodes will be usually aggregated in engine-specific classes.
 * These classes are used primarily to store data, so their variable memebers are public.
 *
 * @package    qtype_preg
 * @copyright  2012 Oleg Sychev, Volgograd State Technical University
 * @author     Oleg Sychev <oasychev@gmail.com>
 * @license    http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
 */

defined('MOODLE_INTERNAL') || die();

global $CFG;
require_once($CFG->dirroot . '/question/type/poasquestion/poasquestion_string.php');
require_once($CFG->dirroot . '/question/type/preg/preg_unicode.php');

/**
 * Represents a node or a lexem position in 2 ways: "absolute" (considering the whole string)
 * and "relative" (considering lines and columns).
 */
class qtype_preg_position {
    /** First index of something (absolute positioning). */
    public $indfirst = -1;
    /** Last index of something (absolute positioning). */
    public $indlast = -1;
    /** Index of the line where something begins. */
    public $linefirst = -1;
    /** Index of the line where something ends. */
    public $linelast = -1;
    /** Index of the first character on the first line. */
    public $colfirst = -1;
    /** Index of the last character on the last line. */
    public $collast = -1;

    public function __construct($indfirst = -1, $indlast = -1, $linefirst = -1, $linelast = -1, $colfirst = -1, $collast = -1) {
        $this->indfirst = $indfirst;
        $this->indlast = $indlast;
        $this->linefirst = $linefirst;
        $this->linelast = $linelast;
        $this->colfirst = $colfirst;
        $this->collast = $collast;
    }

    public function compose($with) {
        return new qtype_preg_position($this->indfirst, $with->indlast,
                                       $this->linefirst, $with->linelast,
                                       $this->colfirst, $with->collast);
    }

    public function add_chars_left($count) {
        return new qtype_preg_position($this->indfirst + $count, $this->indlast,
                                       $this->linefirst, $this->linelast,
                                       $this->colfirst + $count, $this->collast);
    }

    public function add_chars_right($count) {
        return new qtype_preg_position($this->indfirst, $this->indlast + $count,
                                       $this->linefirst, $this->linelast,
                                       $this->colfirst, $this->collast + $count);
    }
}

/**
 * Representation of nodes and leafs as they were typed in the regex.
 */
class qtype_preg_userinscription {
    /** String with the leaf itself. */
    public $data = '';
    /** Subype of the flag in case of \w, \d, [:alnum:] or something. See charset_flag constants. */
    public $isflag = null;

    public function __construct($data = '', $isflag = null) {
        $this->data = $data;
        $this->isflag = $isflag;
    }

    public function __toString() {
        return $this->data;
    }

    /**
     * Checks if it's a simple character like a, b or й.
     */
    public function is_single_character() {
        return $this->isflag === null &&
               textlib::strlen($this->data) == 1;
    }

    public function is_character_range() {
        if ($this->isflag !== null) {
            return false;
        }
        $mpos = textlib::strpos($this->data, '-');
        return $mpos !== null && $mpos > 0 && $mpos < textlib::strlen($this->data) - 1;
    }

    /**
     * Checks if it's a valid (with a special meaning) escape sequence.
     */
    public function is_valid_escape_sequence() {
        if ($this->is_character_range()) {
            return false;
        }
        $allowed = array('a', 'b', 'c', 'e', 'f', 'n', 'r', 't', 'x',
                         'd', 'D', 'h', 'H', 's', 'S', 'v', 'V', 'w', 'W',
                         'p', 'P');
        return textlib::strlen($this->data) > 1 && $this->data[0] == '\\' &&
               (in_array($this->data[1], $allowed) || ctype_digit(textlib::substr($this->data, 1)));
    }

    /**
     * Checks if it's one of the following characters: \a \b \e \f \n \r \t
     */
    public function is_single_escape_sequence_character() {
        if ($this->isflag !== null || !$this->is_valid_escape_sequence()) {
            return false;
        }
        $allowed = array('a', 'b', 'e', 'f', 'n', 'r', 't');
        return in_array($this->data[1], $allowed);
    }

    /**
     * Checks if it's a character represented as \cx
     */
    public function is_single_escape_sequence_character_c() {
        if ($this->isflag !== null || !$this->is_valid_escape_sequence()) {
            return false;
        }
        return $this->data[1] == 'c';
    }

    /**
     * Checks if it's a character represented as \ddd
     */
    public function is_single_escape_sequence_character_oct() {
        if ($this->isflag !== null || !$this->is_valid_escape_sequence()) {
            return false;
        }
        return ctype_digit(textlib::substr($this->data, 1));
    }

    /**
     * Checks if it's a character represented as \xhh of \x{hh}
     */
    public function is_single_escape_sequence_character_hex() {
        if ($this->isflag !== null || !$this->is_valid_escape_sequence()) {
            return false;
        }
        return $this->data[1] == 'x';
    }

    public function is_posix_flag() {
        return $this->isflag !== null && $this->data[0] == '[';
    }

    public function is_uprop_flag() {
        return $this->isflag !== null && $this->data[0] == '\\' && ($this->data[1] == 'p' || $this->data[1] == 'P');
    }

    public function is_slash_flag() {
        return $this->isflag !== null && !$this->is_uprop_flag() && $this->data[0] == '\\';
    }

    public function is_flag_negative() {
        if (!$this->isflag) {
            return false;
        }
        if ($this->data[0] == '\\') {
            return ctype_upper($this->data[1]); // Fortunately, this works both for \W and, for example, \PL    TODO: \Z, \A
        }
        if ($this->data[0] == '[') {
            return $this->data[2] == '^';
        }
        return false;
    }

    public function lang_key($usedescription = false) {
        if ($this->isflag === null || !$usedescription) {
            return $this->isflag;
        }
        $result = 'description_charflag_' . $this->isflag;
        if ($this->is_flag_negative()) {
            $result .= '_neg';
        }
        return $result;
    }
}

/**
 * Class for plain lexems (not complete nodes), they contain position information too.
 */
class qtype_preg_lexem {
    /** An instance of qtype_preg_position. */
    public $position = null;
    /** An instance of qtype_preg_userinscription. */
    public $userinscription = null;

    /**
     * Sets position and userinscription for the node.
     */
    public function set_user_info($position, $userinscription = array()) {
        $this->position = $position;
        $this->userinscription = $userinscription;
    }
}

/**
 * The interface for objects that are passed to qtype_preg_leaf::match(), qtype_preg_leaf::consumes(), qtype_preg_leaf::next_character() as $matcherstateobj.
 */
interface qtype_preg_matcher_state {

    /**
     * Returns index of the first character matched for the given subexpression.
     */
    public function index_first($subexpression = 0);

    /**
     * Returns the length of the given subexpression.
     */
    public function length($subexpression = 0);

    /**
     * Returns whether the given subexpression is captured.
     */
    public function is_subexpr_captured($subexpression);
}

/**
 * Generic node class.
 */
abstract class qtype_preg_node {

    /** A character or a character set. */
    const TYPE_LEAF_CHARSET = 'leaf_charset';
    /** Meta-character or escape sequence matching with a set of characters that couldn't be enumerated. */
    const TYPE_LEAF_META = 'leaf_meta';
    /** Simple assert: ^ $ or escape-sequence. */
    const TYPE_LEAF_ASSERT = 'leaf_assert';
    /** Back reference to a subexpression. */
    const TYPE_LEAF_BACKREF = 'leaf_backref';
    /** Recursive match. */
    const TYPE_LEAF_RECURSION = 'leaf_recursion';
    /** Backtracking control, newline conventions etc sequences. */
    const TYPE_LEAF_CONTROL = 'leaf_control';
    /** Option set. */
    const TYPE_LEAF_OPTIONS = 'leaf_options';
    /** Finite quantifier. */
    const TYPE_NODE_FINITE_QUANT = 'node_finite_quant';
    /** Infinite quantifier. */
    const TYPE_NODE_INFINITE_QUANT = 'node_infinite_quant';
    /** Concatenation. */
    const TYPE_NODE_CONCAT = 'node_concat';
    /** Alternation. */
    const TYPE_NODE_ALT = 'node_alt';
    /** Assert with expression within. */
    const TYPE_NODE_ASSERT = 'node_assert';
    /** Subexpression. */
    const TYPE_NODE_SUBEXPR = 'node_subexpr';
    /** Conditional subexpression. */
    const TYPE_NODE_COND_SUBEXPR = 'node_cond_subexpr';
    /** Error node. */
    const TYPE_NODE_ERROR = 'node_error';

    /** Type one the node - should be equal to a constant defined in this class. */
    public $type;
    /** Subtype, defined by a child class. */
    public $subtype;
    /** Errors found for this particular node. */
    public $errors = array();
    /** An instance of qtype_preg_position. */
    public $position = null;
    /** An instance of qtype_preg_userinscription. */
    public $userinscription = null;
    /** Identifier of this node. */
    public $id = -1;
    /** Subpattern number. */
    public $subpattern = -1;
    /** Some calculable values needed for nfa/dfa construction. */
    public $nullable = null;
    public $firstpos = null;
    public $lastpos = null;

    public function __construct() {

    }

    public function __clone() {
        if ($this->position !== null) {
            $this->position = clone $this->position;
        }
    }

    /**
     * Is this node a subpattern? According to Fowler, a subpattern
     * is a leaf, or a subexpression, or a quantifier.
     */
    abstract public function is_subpattern();

    /**
     * Calculates nullable, firstpos, lastpos and followpos for this node.
     * @param followpos array to store the followpos map.
     */
    abstract public function calculate_nflf(&$followpos);

    /**
     * Finds the nearest suitable subtree by given indexes in the regex string. If the node is N-ary,
     * expands it to be binary for better precision, thus AST is modified. All passed indexes are updated
     * to the indexes of the found subtree.
     */
    public function node_by_regex_fragment($indexfirst, $indexlast, &$idcounter) {
        if ($indexfirst - $indexlast == 1) {
            // Special case: fictive leaves.
            $current = array($this);
            while (count($current) > 0) {
                $tmp = array_pop($current);
                if ($tmp->position->indfirst == $indexfirst && $tmp->position->indlast == $indexlast) {
                    return $tmp;
                }
                if (is_a($tmp, 'qtype_preg_operator')) {
                    $current = array_merge($current, $tmp->operands);
                }
            }
            return null;
        }

        $result = $this;
        $found = is_a($result, 'qtype_preg_leaf');

        // Go down the tree.
        while (!$found) {
            $replaced = false;
            foreach ($result->operands as $operand) {
                $better_than_result = ($operand->position->indfirst >= $result->position->indfirst) && ($operand->position->indlast <= $result->position->indlast);

                $suits_needed = ($operand->position->indfirst <= $indexfirst) && ($operand->position->indlast >= $indexlast);

                if ($better_than_result && $suits_needed) {
                    $result = $operand;
                    $replaced = true;
                }
            }
            $found = !$replaced || is_a($result, 'qtype_preg_leaf');
        }

        $found = ($result->position->indfirst <= $indexfirst) && ($result->position->indlast >= $indexlast);

        if (!$found) {
            return null;
        }

        // Expand N-ary nodes for better precision.
        if (is_a($result, 'qtype_preg_operator')) {
            $count = count($result->operands);
            $from = 0;
            $to = $count - 1;

            for ($i = 0; $i < $count; $i++) {
                $operand = $result->operands[$i];
                if ($operand->position->indfirst <= $indexfirst) {
                    $from = $i;
                }
                $operand = $result->operands[$count - $i - 1];
                if ($operand->position->indlast >= $indexlast) {
                    $to = $count - $i - 1;
                }
            }
            $result->expand($from, $to, $idcounter);

            // Update the result again.
            foreach ($result->operands as $operand) {
                $better_than_result = ($operand->position->indfirst >= $result->position->indfirst) && ($operand->position->indlast <= $result->position->indlast);
                $suits_needed = ($operand->position->indfirst <= $indexfirst) && ($operand->position->indlast >= $indexlast);
                if ($better_than_result && $suits_needed) {
                    $result = $operand;
                }
            }
        }

        return $result;
    }

    /**
     * Expands the subtrees of operands at the given indexes.
     */
    public function expand($from, $to, &$idcounter, $expandsubtree = false) {
    }

    /**
     * Expands the subtrees of all operands.
     */
    public function expand_all(&$idcounter, $expandsubtree = false) {
    }

    /**
     * Sets position and userinscription for the node.
     */
    public function set_user_info($position, $userinscription = array()) {
        $this->position = $position;
        $this->userinscription = $userinscription;
    }

    /**
     * Returns the key for this node in the lang file.
     */
    public function lang_key($usedescription = false) {
        return $usedescription ? 'description_' . $this->subtype : $this->subtype;
    }

    /**
     * May be overloaded by childs to change name using data from $this->pregnode.
     */
    public function ui_nodename() {
        return get_string($this->type, 'qtype_preg');
    }
}

/**
 * Generic leaf class.
 */
abstract class qtype_preg_leaf extends qtype_preg_node {

    /** Constants that can be returned from next_character for special cases. */
    const NEXT_CHAR_CANNOT_GENERATE = 0x01;
    const NEXT_CHAR_NOT_NEEDED      = 0x02;
    const NEXT_CHAR_END_HERE        = 0x04;

    /** Is matching case insensitive? */
    public $caseless = false;
    /** Is this leaf negative? */
    public $negative = false;
    /** Assertions merged into this node (qtype_preg_leaf_assert objects). */
    public $mergedassertions = array();//TODO two fields: assertionsbefore and assertionsafter.

    public function __clone() {
        parent::__clone();
        // When clonning a leaf we also want the merged assertions to be cloned.
        foreach ($this->mergedassertions as $i => $mergedassertion) {
            $this->mergedassertions[$i] = clone $mergedassertion;
        }
    }

    public function is_subpattern() {
        return true;    // Any leaf is a subpattern.
    }

    public function calculate_nflf(&$followpos) {
        // The following is true for almost all leafs, except emptiness.
        $this->nullable = false;
        $this->firstpos = array($this->id);
        $this->lastpos = array($this->id);
    }

    public function lang_key($usedescription = false) {
        $result = parent::lang_key($usedescription);
        if ($usedescription && $this->negative) {
            $result .= '_neg';
        }
        return $result;
    }

    /**
     * Returns the number of characters consumed by this leaf: 0 in case of an assertion or eps-leaf,
     * 1 in case of a single character, n in case of a backreferense.
     * @param matcherstateobj an object which implements qtype_preg_matcher_state interface.
     * @return number of characters consumed by this leaf.
     */
    public function consumes($matcherstateobj = null) {
        return 1;
    }

    /**
     * Returns true if character(s) starting from $str[$pos] match(es) this leaf, false otherwise
     * Contains universal code to deal with merged assertions. Overload match_inner to define your leaf type matching
     * @param str the string being matched.
     * @param pos position of character in the string, if leaf is non-consuming than position before this character is analyzed.
     * @param length an integer variable to store the length of the match.
     * @param matcherstateobj an object which implements the qtype_preg_matcher_state interface.
     */
    public function match($str, $pos, &$length, $matcherstateobj = null) {
        $result = true;
        // Check merged assertions first.
        foreach ($this->mergedassertions as $assert) {
            $result = $result && $assert->match($str, $pos, $length, $matcherstateobj);
        }
        // Now check this leaf.
        $result = $result && $this->match_inner($str, $pos, $length, $matcherstateobj);
        return $result;
    }

    /**
     * Returns true if character(s) starting from $str[$pos] matches with leaf, false otherwise
     * Implements details of a particular leaf matching.
     * @param str the string being matched.
     * @param pos position of character in the string, if leaf is non-consuming than position before this character is analyzed.
     * @param length an integer variable to store the length of the match.
     * @param matcherstateobj an object which implements the qtype_preg_matcher_state interface.
     */
    abstract protected function match_inner($str, $pos, &$length, $matcherstateobj = null);

    /**
     * Returns a character suitable for both this leaf and merged assertions and the previous character.
     * @param str string already matched.
     * @param pos position of the last matched character in the string.
     * @param length number of characters matched (can be greater than 0 in case of a partial backreference match).
     * @param matcherstateobj an object which implements the qtype_preg_matcher_state interface.
     */
    abstract public function next_character($str, $pos, $length = 0, $matcherstateobj = null);

    /**
     * Returns a human-readable form of this leaf.
     * @return human-readable string describing this leaf.
     */
    abstract public function tohr();
}

/**
 * Defines operator nodes.
 */
abstract class qtype_preg_operator extends qtype_preg_node {

    /** An array of operands. */
    public $operands = array();

    public function __clone() {
        parent::__clone();
        // When clonning an operator we also want its subtree to be cloned.
        foreach ($this->operands as $i => $operand) {
            $this->operands[$i] = clone $operand;
        }
    }

    public function calculate_nflf(&$followpos) {
        // Calculate nflf for all operands.
        foreach ($this->operands as $operand) {
            $operand->calculate_nflf($followpos);
        }
        if (count($this->operands) > 0) {
            $this->nullable = $this->operands[0]->nullable;
            $this->firstpos = $this->operands[0]->firstpos;
            $this->lastpos = $this->operands[0]->lastpos;
        } else {
            $this->nullable =  false;
            $this->firstpos = array();
            $this->lastpos = array();
        }
    }

    public function expand($from, $to, &$idcounter, $expandsubtree = false) {
        if ($expandsubtree) {
            for ($i = $from; $i <= $to; $i++) {
                $this->operands[$i]->expand_all($idcounter, $expandsubtree);
            }
        }

        if (count($this->operands) <= 2) {
            return;
        }

        $operands = array();

        // Copy 'left' operands.
        for ($i = 0; $i < $from; $i++) {
            $operands[] = $this->operands[$i];
        }

        // Form the new subtree and add it as operand.
        $newnode = clone $this; // Will go down the tree.
        $newnode->id = ++$idcounter;
        $newnode->operands = array();
        for ($i = $from; $i <= $to; $i++) {
            $newnode->operands[] = $this->operands[$i];
        }
        $operands[] = $newnode;

        // Copy 'right' operands.
        for ($i = $to + 1; $i < count($this->operands); $i++) {
            $operands[] = $this->operands[$i];
        }

        // Update operands of this node.
        $this->operands = $operands;
        if ($expandsubtree) {
        	$newnode->expand(0, count($newnode->operands) - 2, $idcounter);
        }

        // Fix the new node position.
        $left = $newnode->operands[0];
        $right = $newnode->operands[count($newnode->operands) - 1];
        $newnode->position = new qtype_preg_position($left->position->indfirst, $right->position->indlast,
                                                     $left->position->linefirst, $right->position->linelast,
                                                     $left->position->colfirst, $right->position->collast);

        if (count($operands) == 1) {
            $this->operands = $newnode->operands;
        }
    }

    public function expand_all(&$idcounter, $expandsubtree = false) {
        $this->expand(0, count($this->operands) - 1, $idcounter, $expandsubtree);
    }
}

/**
 * Represents a character or a charcter set.
 */
class qtype_preg_leaf_charset extends qtype_preg_leaf {

    /** Simple flags in the disjunctive normal form. */
    public $flags = null;   // array(array());
    /** A range is a pair of integers, ranges are 3-dimensional array of integers or 2-dimensional array of pairs. */
    protected $ranges = array();
    /** Array of assertion flags (it's impossible to calculate an assertion as a range), each asserts[i] is an array of 0/1/2 asserts as flags; for ranges[i]. */
    protected $asserts = array();
    /** true if the charset is a DNF range matrix, false if charset is DNF of flags. */
    public $israngecalculated = true;

    public function __construct() {
        $this->type = qtype_preg_node::TYPE_LEAF_CHARSET;
    }

    public function __clone() {
        parent::__clone();
        if ($this->flags !== null) {
            foreach ($this->flags as $ind1 => $extflag) {
                $cur = array();
                foreach ($extflag as $ind2 => $inflag) {
                    $cur[$ind2] = clone $inflag;
                }
                $this->flags[$ind1] = $cur;
            }
        }
    }

    public function is_single_character() {
        return count($this->flags) == 1 &&
               $this->flags[0][0]->type == qtype_preg_charset_flag::TYPE_SET &&
               $this->flags[0][0]->data->length() == 1;
    }

    public function is_single_printable_character() {
        if (!$this->is_single_character()) {
            return false;
        }
        return !qtype_preg_unicode::is_in_range($this->flags[0][0]->data[0], qtype_preg_unicode::Z_ranges()) &&
               !qtype_preg_unicode::is_in_range($this->flags[0][0]->data[0], qtype_preg_unicode::C_ranges());
    }

    public function is_single_non_printable_character() {
        if (!$this->is_single_character()) {
            return false;
        }
        return qtype_preg_unicode::is_in_range($this->flags[0][0]->data[0], qtype_preg_unicode::Z_ranges()) ||
               qtype_preg_unicode::is_in_range($this->flags[0][0]->data[0], qtype_preg_unicode::C_ranges());
    }

    /**
     * Checks if it's a single \a \b \e \f \r \t
     */
    public function is_single_escape_sequence_character() {
        if (!$this->is_single_character()) {
            return false;
        }
        return in_array($this->userinscription[0]->data, qtype_preg_lexer::char_escape_sequences_inside_charset());
    }

    public function is_single_flag() {
        return count($this->flags) == 1 &&
               $this->flags[0][0]->type == qtype_preg_charset_flag::TYPE_FLAG &&
               $this->flags[0][0]->data != qtype_preg_charset_flag::META_DOT;
    }

    public function is_single_dot() {
        return count($this->flags) == 1 &&
               $this->flags[0][0]->type == qtype_preg_charset_flag::TYPE_FLAG &&
               $this->flags[0][0]->data == qtype_preg_charset_flag::META_DOT;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        if ($pos < 0 || $pos >= $str->length()) {
            return false;
        }
        if ($this->flags === null) {
            return false;
        }

        foreach ($this->flags as $flags) {
            // Get intersection of all current flags.
            $result = !empty($flags);
            foreach ($flags as $flag) {
                $result = $result && $flag->match($str, $pos, $this->caseless);
                if (!$result) {
                    break;
                }
            }
            $result = ($result xor $this->negative);
            if ($result) {
                $length = 1;
                return true;
            }
        }

        $length = 0;
        return false;
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) { // TODO may be rename to character?
        $desired_chars = array(array(0x21, 0x007F));
        $desired_whitespaces = array(array(0x20, 0x20));

        foreach ($this->flags as $flags) {
            // Get intersection of all current flags.
            $ranges = qtype_preg_unicode::dot_ranges();

            foreach ($flags as $flag) {
                if ($flag->type === qtype_preg_charset_flag::TYPE_SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                if ($flag->negative) {
                    $currange = qtype_preg_unicode::negate_ranges($currange);
                }
                $ranges = qtype_preg_unicode::intersect_ranges($ranges, $currange);
            }
            if ($this->negative) {
                $ranges = qtype_preg_unicode::negate_ranges($ranges);
            }

            $desired = qtype_preg_unicode::intersect_ranges($ranges, $desired_chars);
            if (!empty($desired)) {
                $code = $desired[0][0];
                return new qtype_poasquestion_string(qtype_preg_unicode::code2utf8($code));
            }

            $desired = qtype_preg_unicode::intersect_ranges($ranges, $desired_whitespaces);
            if (!empty($desired)) {
                $code = $desired[0][0];
                return new qtype_poasquestion_string(qtype_preg_unicode::code2utf8($code));
            }

            if (!empty($ranges)) {
                $code = $ranges[0][0];
                return new qtype_poasquestion_string(qtype_preg_unicode::code2utf8($code));
            }

            // Check all the returned ranges.
            /*foreach ($ranges as $range) {
                for ($i = $range[0]; $i <= $range[1]; $i++) {
                    $c = new qtype_poasquestion_string(qtype_preg_unicode::code2utf8($i));
                    // if ($this->match($c, 0, $l)) {
                    return $c;
                    // }
                }
            }*/
        }
        return new qtype_poasquestion_string('');
    }

    /**
     * Check if other charset is included in this. That means that any character matching other also matches this.
     * @param other charset to check.
     * @return true if included, false otherwise.
     */
    public function is_include(qtype_preg_leaf_charset $other) {
        /*$result = true;
        for ($i = 32; $result && $i < 126; $i++) {
            $c = new qtype_poasquestion_string(chr($i));
            $result = $result && (!$this->match($c, 0, $l) && $other->match($c, 0, $l));
        }
        return $result || $other===$this;*/
        // Getting ranges of this charset.
        foreach ($this->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::TYPE_SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $ranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($this->negative) {
                    foreach ($ranges as &$tmp) {
                        $tmp['negative'] = true;
                    }
                    $ranges = qtype_preg_unicode::intersect_ranges($ranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        // Getting ranges of other charset.
        foreach ($other->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::TYPE_SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $otherranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($other->negative) {
                    foreach ($otherranges as &$tmp) {
                        $tmp['negative'] = true;
                    }
                    $otherranges = qtype_preg_unicode::intersect_ranges($otherranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        // Comparing ranges of this and other charsets.
        if (is_array($ranges)) {
              $included = true;
        } else {
            return false;
        }
        /*foreach($ranges as $i=>$ran) {
               $ranges[$i] = array ('negative'=>false, 0=>$ranges[$i][0], 1=>$ranges[$i][1]);
        }
        foreach($otherranges as $i=>$ran) {
               $otherranges[$i] = array ('negative'=>false, 0=>$otherranges[$i][0], 1=>$otherranges[$i][1]);
        }
        $ranges = qtype_preg_unicode::intersect_ranges(array($ranges, $otherranges));*/
        for (reset($ranges), reset($otherranges); $included && current($ranges)!==false; next($ranges), next($otherranges)) {
            if (current($ranges)!=current($otherranges)) {
                $included = false;
                /*while (next($ranges)!==false && current($ranges)!=current($otherranges)) {
                    next($ranges);
                }
                if (current($ranges)!==false) {
                $included = true;
                }*/
            }
        }
        return $included;
    }
    public function is_part_ident(qtype_preg_leaf_charset $other) {
        /*$flag1 = false;
        $flag2 = false;
        for ($i = 32; !($flag1 && $flag2) && $i < 126; $i++) {
            $c=chr($i);
            $flag1 = $flag1 || ($this->match($c, 0, $l) && $other->match($c, 0, $l));
            $flag2 = $flag2 || (!$this->match($c, 0, $l) && $other->match($c, 0, $l) || $this->match($c, 0, $l) && !$other->match($c, 0, $l));
        }
        return $flag1 && $flag2;*/
        foreach ($this->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::TYPE_SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $ranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($this->negative) {
                    foreach ($ranges as &$tmp) {
                        $tmp['negative'] = true;
                    }
                    $ranges = qtype_preg_unicode::intersect_ranges($ranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        // Getting ranges of other charset.
        foreach ($other->flags as $flags) {
            foreach ($flags as $flag) {
                // Get intersection of all current flags.
                $range = array(array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                if ($flag->type === qtype_preg_charset_flag::TYPE_SET) {
                    $currange = qtype_preg_unicode::get_ranges_from_charset($flag->data);
                } else {
                    $currange = call_user_func('qtype_preg_unicode::' . $flag->data . '_ranges');
                }
                foreach ($currange as &$tmp) {
                    $tmp['negative'] = $flag->negative;
                }
                $otherranges = qtype_preg_unicode::intersect_ranges($range, $currange);
                if ($other->negative) {
                    foreach ($otherranges as &$tmp) {
                        $tmp['negative'] = true;
                    }
                    $otherranges = qtype_preg_unicode::intersect_ranges($otherranges, array('negative' => false, 0 => 0, 1 => qtype_preg_unicode::max_possible_code()));
                }
            }
        }
        // Comparing ranges of this and other charsets.
        if (is_array($ranges)) {
              $included = false;
        } else {
            return false;
        }
        /*foreach($ranges as $i=>$ran) {
               $ranges[$i] = array ('negative'=>false, 0=>$ranges[$i][0], 1=>$ranges[$i][1]);
        }
        foreach($otherranges as $i=>$ran) {
               $otherranges[$i] = array ('negative'=>false, 0=>$otherranges[$i][0], 1=>$otherranges[$i][1]);
        }
        $ranges = qtype_preg_unicode::intersect_ranges(array($ranges, $otherranges));*/
        for (reset($ranges), reset($otherranges); $included && current($ranges)!==false; next($ranges), next($otherranges)) {
            if (current($ranges)==current($otherranges)) {
                $included = true;
                /*while (next($ranges)!==false && current($ranges)!=current($otherranges)) {
                    next($ranges);
                }
                if (current($ranges)!==false) {
                $included = true;
                }*/
            }
        }
        return $included;
    }

    public function tohr() {
        $result = '';
        foreach ($this->flags as $ind1 => $extflag) {
            $cur = '';
            foreach ($extflag as $ind2 => $inflag) {
                $cur .= $inflag->tohr();
                if ($ind2 != count($extflag) - 1) {
                    $cur .= '&&';
                }
            }
            $result .= $cur;
            if ($ind1 != count($this->flags) - 1) {
                $result .= ' || ';
            }
        }
        return $result;
    }

    /**
     * Intersects this charset with other one.
     * @param other charset to intersect with.
     * @return an object of qtype_preg_leaf_charset which is the intersection of this and other.
     */
    public function intersect(qtype_preg_leaf_charset $other) {
        if ($this->negative) {
            $this->push_negative();
        }
        if ($other->negative) {
            $other->push_negative();
        }
        foreach ($this->flags as $disjunct1) {
            foreach ($other->flags as $disjunct2) {
                $resflags[] = array_merge($disjunct1, $disjunct2);
            }
        }
        $result = new qtype_preg_leaf_charset;
        $result->flags = $resflags;
        $result->israngecalculated = false;
        return $result;
    }

    /**
     * Substracts other charset from this.
     * @param other charset to substract.
     * @return an object of qtype_preg_leaf_charset which is the substraction of this and other.
     */
    public function substract(qtype_preg_leaf_charset $other) {
        $other->negative = !$other->negative;
        $result = $this->intersect($other);
        $other->negative = !$other->negative;
        return $result;
    }
}

/**
 * Represents a part of a charset - can be a numerable characters, flag like \w, \d or a unicode property.
 */
class qtype_preg_charset_flag {

    // Charset types.
    const TYPE_SET               = 'enumerable_characters';
    const TYPE_FLAG              = 'functionally_calculated_characters';

    const META_DOT               = 'dot';

    // Escape sequences.
    const SLASH_D                = 'slashd';
    const SLASH_H                = 'slashh';
    const SLASH_S                = 'slashs';
    const SLASH_V                = 'slashv';
    const SLASH_W                = 'slashw';

    // POSIX classes.
    const POSIX_ALNUM            = 'alnum';      // [:alnum:]
    const POSIX_ALPHA            = 'alpha';      // [:alpha:]
    const POSIX_ASCII            = 'ascii';      // [:ascii:]
    const POSIX_BLANK            = 'blank';      // [:blank:]
    const POSIX_CNTRL            = 'cntrl';      // [:cntrl:]
    const POSIX_DIGIT            = 'digit';      // [:digit:]
    const POSIX_GRAPH            = 'graph';      // [:graph:]
    const POSIX_LOWER            = 'lower';      // [:lower:]
    const POSIX_PRINT            = 'print';      // [:print:]
    const POSIX_PUNCT            = 'punct';      // [:punct:]
    const POSIX_SPACE            = 'space';      // [:space:]
    const POSIX_UPPER            = 'upper';      // [:upper:]
    const POSIX_WORD             = 'word';       // [:word:]
    const POSIX_XDIGIT           = 'xdigit';     // [:xdigit:]

    const UPROPCC                = 'Cc';         // Control
    const UPROPCF                = 'Cf';         // Format
    const UPROPCN                = 'Cn';         // Unassigned
    const UPROPCO                = 'Co';         // Private use
    const UPROPCS                = 'Cs';         // Surrogate
    const UPROPC                 = 'C';          // Other
    const UPROPLL                = 'Ll';         // Lower case letter
    const UPROPLM                = 'Lm';         // Modifier letter
    const UPROPLO                = 'Lo';         // Other letter
    const UPROPLT                = 'Lt';         // Title case letter
    const UPROPLU                = 'Lu';         // Upper case letter
    const UPROPL                 = 'L';          // Letter
    const UPROPMC                = 'Mc';         // Spacing mark
    const UPROPME                = 'Me';         // Enclosing mark
    const UPROPMN                = 'Mn';         // Non-spacing mark
    const UPROPM                 = 'M';          // Mark
    const UPROPND                = 'Nd';         // Decimal number
    const UPROPNL                = 'Nl';         // Letter number
    const UPROPNO                = 'No';         // Other number
    const UPROPN                 = 'N';          // Number
    const UPROPPC                = 'Pc';         // Connector punctuation
    const UPROPPD                = 'Pd';         // Dash punctuation
    const UPROPPE                = 'Pe';         // Close punctuation
    const UPROPPF                = 'Pf';         // Final punctuation
    const UPROPPI                = 'Pi';         // Initial punctuation
    const UPROPPO                = 'Po';         // Other punctuation
    const UPROPPS                = 'Ps';         // Open punctuation
    const UPROPP                 = 'P';          // Punctuation
    const UPROPSC                = 'Sc';         // Currency symbol
    const UPROPSK                = 'Sk';         // Modifier symbol
    const UPROPSM                = 'Sm';         // Mathematical symbol
    const UPROPSO                = 'So';         // Other symbol
    const UPROPS                 = 'S';          // Symbol
    const UPROPZL                = 'Zl';         // Line separator
    const UPROPZP                = 'Zp';         // Paragraph separator
    const UPROPZS                = 'Zs';         // Space separator
    const UPROPZ                 = 'Z';          // Separator
    const UPROPXAN               = 'Xan';        // Any alphanumeric character
    const UPROPXPS               = 'Xps';        // Any POSIX space character
    const UPROPXSP               = 'Xsp';        // Any Perl space character
    const UPROPXWD               = 'Xwd';        // Any Perl "word" character
    const ARABIC                 = 'Arabic';
    const ARMENIAN               = 'Armenian';
    const AVESTAN                = 'Avestan';
    const BALINESE               = 'Balinese';
    const BAMUM                  = 'Bamum';
    const BENGALI                = 'Bengali';
    const BOPOMOFO               = 'Bopomofo';
    const BRAILLE                = 'Braille';
    const BUGINESE               = 'Buginese';
    const BUHID                  = 'Buhid';
    const CANADIAN_ABORIGINAL    = 'Canadian_Aboriginal';
    const CARIAN                 = 'Carian';
    const CHAM                   = 'Cham';
    const CHEROKEE               = 'Cherokee';
    const COMMON                 = 'Common';
    const COPTIC                 = 'Coptic';
    const CUNEIFORM              = 'Cuneiform';
    const CYPRIOT                = 'Cypriot';
    const CYRILLIC               = 'Cyrillic';
    const DESERET                = 'Deseret';
    const DEVANAGARI             = 'Devanagari';
    const EGYPTIAN_HIEROGLYPHS   = 'Egyptian_Hieroglyphs';
    const ETHIOPIC               = 'Ethiopic';
    const GEORGIAN               = 'Georgian';
    const GLAGOLITIC             = 'Glagolitic';
    const GOTHIC                 = 'Gothic';
    const GREEK                  = 'Greek';
    const GUJARATI               = 'Gujarati';
    const GURMUKHI               = 'Gurmukhi';
    const HAN                    = 'Han';
    const HANGUL                 = 'Hangul';
    const HANUNOO                = 'Hanunoo';
    const HEBREW                 = 'Hebrew';
    const HIRAGANA               = 'Hiragana';
    const IMPERIAL_ARAMAIC       = 'Imperial_Aramaic';
    const INHERITED              = 'Inherited';
    const INSCRIPTIONAL_PAHLAVI  = 'Inscriptional_Pahlavi';
    const INSCRIPTIONAL_PARTHIAN = 'Inscriptional_Parthian';
    const JAVANESE               = 'Javanese';
    const KAITHI                 = 'Kaithi';
    const KANNADA                = 'Kannada';
    const KATAKANA               = 'Katakana';
    const KAYAH_LI               = 'Kayah_Li';
    const KHAROSHTHI             = 'Kharoshthi';
    const KHMER                  = 'Khmer';
    const LAO                    = 'Lao';
    const LATIN                  = 'Latin';
    const LEPCHA                 = 'Lepcha';
    const LIMBU                  = 'Limbu';
    const LINEAR_B               = 'Linear_B';
    const LISU                   = 'Lisu';
    const LYCIAN                 = 'Lycian';
    const LYDIAN                 = 'Lydian';
    const MALAYALAM              = 'Malayalam';
    const MEETEI_MAYEK           = 'Meetei_Mayek';
    const MONGOLIAN              = 'Mongolian';
    const MYANMAR                = 'Myanmar';
    const NEW_TAI_LUE            = 'New_Tai_Lue';
    const NKO                    = 'Nko';
    const OGHAM                  = 'Ogham';
    const OLD_ITALIC             = 'Old_Italic';
    const OLD_PERSIAN            = 'Old_Persian';
    const OLD_SOUTH_ARABIAN      = 'Old_South_Arabian';
    const OLD_TURKIC             = 'Old_Turkic';
    const OL_CHIKI               = 'Ol_Chiki';
    const ORIYA                  = 'Oriya';
    const OSMANYA                = 'Osmanya';
    const PHAGS_PA               = 'Phags_Pa';
    const PHOENICIAN             = 'Phoenician';
    const REJANG                 = 'Rejang';
    const RUNIC                  = 'Runic';
    const SAMARITAN              = 'Samaritan';
    const SAURASHTRA             = 'Saurashtra';
    const SHAVIAN                = 'Shavian';
    const SINHALA                = 'Sinhala';
    const SUNDANESE              = 'Sundanese';
    const SYLOTI_NAGRI           = 'Syloti_Nagri';
    const SYRIAC                 = 'Syriac';
    const TAGALOG                = 'Tagalog';
    const TAGBANWA               = 'Tagbanwa';
    const TAI_LE                 = 'Tai_Le';
    const TAI_THAM               = 'Tai_Tham';
    const TAI_VIET               = 'Tai_Viet';
    const TAMIL                  = 'Tamil';
    const TELUGU                 = 'Telugu';
    const THAANA                 = 'Thaana';
    const THAI                   = 'Thai';
    const TIBETAN                = 'Tibetan';
    const TIFINAGH               = 'Tifinagh';
    const UGARITIC               = 'Ugaritic';
    const VAI                    = 'Vai';
    const YI                     = 'Yi';

    /** Is this flag negative? */
    public $negative = false;
    /** Type of this flag, can be either TYPE_SET or TYPE_FLAG. */
    public $type;
    /** Characters, flag or unicode property if this is a TYPE_SET, TYPE_FLAG correspondingly. */
    public $data;


    public function __clone() {
        if (is_object($this->data)) {
            $this->data = clone $this->data;
        }
    }

    /**
     * Sets the subtype and the data of this flag.
     * @param type a constant defining the subtype of this flag.
     * @param data the concrete value of this flag - characters, a flag or a unicode property.
     */
    public function set_data($type, $data) {
        $this->type = $type;
        $this->data = $data;
    }

    public function match($str, $pos, $caseless) {
        if ($pos < 0 || $pos >= $str->length()) {
            return false;    // String index out of borders.
        }

        $char = $str[$pos];
        if ($caseless) {
            $charlower = qtype_poasquestion_string::strtolower($char);
            $charupper = qtype_poasquestion_string::strtoupper($char);
        }

        switch ($this->type) {
            case self::TYPE_SET:
                $ranges = qtype_preg_unicode::get_ranges_from_charset($this->data);
                break;
            case self::TYPE_FLAG:
                $ranges = call_user_func('qtype_preg_unicode::' . $this->data . '_ranges');
                break;
        }

        if ($caseless) {
            $result = qtype_preg_unicode::is_in_range($charlower, $ranges) || qtype_preg_unicode::is_in_range($charupper, $ranges);
        } else {
            $result = qtype_preg_unicode::is_in_range($char, $ranges);
        }
        return ($result xor $this->negative);
    }

    public function tohr() {
        $result = '';
        switch ($this->type) {
            case self::TYPE_SET:
                $result = $this->data;
                break;
            case self::TYPE_FLAG:
                $result = $this->data;
                break;
            default:
                return '';
        }
        if ($this->negative) {
            $result = '!' . $result;
        }
        return $result;
    }
}

/**
 * Defines meta-characters that can't be enumerated.
 */
class qtype_preg_leaf_meta extends qtype_preg_leaf {

    // Leaf with empty in alternation (something|).
    const SUBTYPE_EMPTY = 'empty_leaf_meta';
    // Service subtype - end of regex, but not end of string.
    const SUBTYPE_ENDREG = 'endreg_leaf_meta';

    public function __construct($subtype = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_META;
        $this->subtype = $subtype;
    }

    public function calculate_nflf(&$followpos) {
        parent::calculate_nflf($followpos);
        if ($this->subtype == self::SUBTYPE_EMPTY) {
            $this->nullable = true;
            $this->firstpos = array();
            $this->lastpos = array();
        }
    }

    // TODO - ui_nodename().

    public function consumes($matcherstateobj = null) {
        return 0;
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return new qtype_poasquestion_string('');
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        return true;
    }

    public function tohr() {
        switch ($this->subtype) {
            case self::SUBTYPE_ENDREG:
                return 'metaENDREG';
            case self::SUBTYPE_EMPTY:
                return 'metaEPS';
            default:
                return '';
        }
    }
}

/**
 * Base class for simple assertions.
 */
abstract class qtype_preg_leaf_assert extends qtype_preg_leaf {

    /** \b and \B */
    const SUBTYPE_ESC_B = 'esc_b_leaf_assert';
    /** \A */
    const SUBTYPE_ESC_A = 'esc_a_leaf_assert';
    /** \z and \Z */
    const SUBTYPE_ESC_Z = 'esc_z_leaf_assert';
    /** \G */
    const SUBTYPE_ESC_G = 'esc_g_leaf_assert';
    /** ^ */
    const SUBTYPE_CIRCUMFLEX = 'circumflex_leaf_assert';
    /** $ */
    const SUBTYPE_DOLLAR = 'dollar_leaf_assert';

    public function __construct($negative = false) {
        $this->type = qtype_preg_node::TYPE_LEAF_ASSERT;
        $this->negative = $negative;
    }

    public function is_start_anchor() {
        return $this->subtype == self::SUBTYPE_ESC_A || $this->subtype == self::SUBTYPE_CIRCUMFLEX;
    }

    public function is_end_anchor() {
        return $this->subtype == self::SUBTYPE_ESC_Z || $this->subtype == self::SUBTYPE_DOLLAR;
    }

    public function consumes($matcherstateobj = null) {
        return 0;
    }
}

/**
 * Simple assertion \B (negative == true) matches at not a word boundary.
 * Simple assertion \b (negative == false) matches at a word boundary.
 */
class qtype_preg_leaf_assert_esc_b extends qtype_preg_leaf_assert {

    public function __construct($negative = false) {
        parent::__construct($negative);
        $this->subtype = self::SUBTYPE_ESC_B;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $alnumrange = qtype_preg_unicode::alnum_ranges();
        $ch0 = $str[0];
        $ch1 = $str[$pos - 1];

        $flag0 = $ch0 == '_' || qtype_preg_unicode::is_in_range($ch0, $alnumrange);
        $flag1 = $ch1 == '_' || qtype_preg_unicode::is_in_range($ch1, $alnumrange);

        $start = $flag0 && $pos == 0;
        $end = $flag1 && $pos == $str->length();
        $wnotw = false;
        $notww = false;

        if ($pos > 0 && $pos < $str->length()) {
            $ch2 = $str[$pos];
            $flag2 = $ch2 == '_' || qtype_preg_unicode::is_in_range($ch2, $alnumrange);
            $wnotw = $flag1 && !$flag2;
            $notww = !$flag1 && $flag2;
        }

        $length = 0;
        return ($start || $end || $wnotw || $notww) xor $this->negative;
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return '';  // TODO
    }

    public function tohr() {
        return $this->negative ? 'assert \B' : 'assert \b';
    }
}

/**
 * Simple assertion \A matches at the very start of the string.
 */
class qtype_preg_leaf_assert_esc_a extends qtype_preg_leaf_assert {

    public function __construct($negative = false) {
        parent::__construct($negative);
        $this->subtype = self::SUBTYPE_ESC_A;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        return ($pos == 0);
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return '';  // TODO
    }

    public function tohr() {
        return 'assert \A';
    }
}

/**
 * Simple assertion \Z (negative == true) matches at the end of the string, also matches before the very last newline.
 * Simple assertion \z (negative == false) matches only at the end of the string.
 */
class qtype_preg_leaf_assert_esc_z extends qtype_preg_leaf_assert {

    public function __construct($negative = false) {
        parent::__construct($negative);
        $this->subtype = self::SUBTYPE_ESC_Z;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        if ($this->negative) {
            return ($pos == $str->length()) || ($pos == $str->length() - 1 && $str[$pos] == "\n");
        } else {
            return ($pos == $str->length());
        }
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return '';  // TODO
    }

    public function tohr() {
        return $this->negative ? 'assert \Z' : 'assert \z';
    }
}

/**
 * Simple assertion \G matches at the first matching position in the string.
 */
class qtype_preg_leaf_assert_esc_g extends qtype_preg_leaf_assert {

    public function __construct($negative = false) {
        parent::__construct($negative);
        $this->subtype = self::SUBTYPE_ESC_G;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        return false; // TODO
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return '';  // TODO
    }

    public function tohr() {
        return 'assert \G';
    }
}

/**
 * Simple assertion ^ matches at the very start of the string or after any \n.
 * Used only in multiline mode.
 */
class qtype_preg_leaf_assert_circumflex extends qtype_preg_leaf_assert {

    public function __construct($negative = false) {
        parent::__construct($negative);
        $this->subtype = self::SUBTYPE_CIRCUMFLEX;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        return ($pos == 0) || ($str[$pos - 1] == "\n");
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return '';  // TODO
    }

    public function tohr() {
        return 'assert ^';
    }
}

/**
 * Simple assertion $ matches at the end of the string and before any \n.
 * Used only in multiline mode.
 */
class qtype_preg_leaf_assert_dollar extends qtype_preg_leaf_assert {

    public function __construct($negative = false) {
        parent::__construct($negative);
        $this->subtype = self::SUBTYPE_DOLLAR;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;
        return ($pos == $str->length()) || ($str[$pos] == "\n");
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        return '';  // TODO
    }

    public function tohr() {
        return 'assert $';
    }
}

/**
 * Defines backreferences.
 */
class qtype_preg_leaf_backref extends qtype_preg_leaf {
    /** The number of a subexpression to refer to. */
    public $number;

    public function __construct($number = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_BACKREF;
        $this->subtype = $this->type;
        $this->number = $number;
    }

    public function lang_key($usedescription = false) {
        $result = parent::lang_key($usedescription);
        if ($usedescription && is_string($this->number)) {
            $result .= '_name';
        }
        return $result;
    }

    public function consumes($matcherstateobj = null) {
        if (!$matcherstateobj->is_subexpr_captured($this->number)) {
            return qtype_preg_matching_results::UNKNOWN_CHARACTERS_LEFT;
        }
        return $matcherstateobj->length($this->number);
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        $length = 0;

        if (!$matcherstateobj->is_subexpr_captured($this->number)) {
            // For no match return the result immediately.
            return false;
        }

        $subexprlen = $matcherstateobj->length($this->number);
        if ($subexprlen == 0) {
            // For empty match return the result immediately.
            return true;
        }

        if ($pos >= $str->length()) {
            // Out of borders.
            return false;
        }

        $start = $matcherstateobj->index_first($this->number);
        $end = $start + $subexprlen - 1;

        $strcopy = clone $str;
        if ($this->caseless) {
            $strcopy->tolower();
        }

        // Check char by char.
        $result = true;
        for ($i = $start; $result && $i <= $end && $length + $pos < $strcopy->length(); $i++) {
            $result = $result && ($strcopy[$i] == $strcopy[$pos + $length]);
            if ($result) {
                $length++;
            } else {
                break;
            }
        }

        // If the string has not enough characters.
        if ($pos + $subexprlen - 1 >= $strcopy->length()) {
            $result = false;
        }

        return $result;
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        // TODO: check for assertions in case of $length == 0
        if (!$matcherstateobj->is_subexpr_captured($this->number)) {
            return new qtype_poasquestion_string('');
        }
        $start = $matcherstateobj->index_first($this->number);
        $end = $start + $matcherstateobj->length($this->number);
        if ($end > $str->length()) {
            return new qtype_poasquestion_string('');
        }
        return $str->substring($start + $length, $end - $start - $length);
    }

    public function tohr() {
        return 'backref #' . $this->number;
    }
}

class qtype_preg_leaf_recursion extends qtype_preg_leaf {

    public $number;

    public function __construct($number = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_RECURSION;
        $this->subtype = $this->type;
        $this->number = $number;
    }

    public function lang_key($usedescription = false) {
        $result = parent::lang_key($usedescription);
        if ($usedescription && $this->number === 0) {
            $result .= '_all';
        } else if ($usedescription && is_string($this->number)) {
            $result .= '_name';
        }
        return $result;
    }

    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        die ('TODO: implement abstract function match for qtype_preg_leaf_recursion class before use it!');
    }

    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        die ('TODO: implement abstract function character for qtype_preg_leaf_recursion class before use it!');
    }

    public function tohr() {
        return 'recursion';
    }
}

/**
 * Reperesents backtracking control, newline convention etc sequences like (*...).
 */
class qtype_preg_leaf_control extends qtype_preg_leaf {

    /** (*ACCEPT) */
    const SUBTYPE_ACCEPT = 'accept_leaf_control';
    /** (*FAIL) */
    const SUBTYPE_FAIL = 'fail_leaf_control';
    /** (*MARK:NAME) */
    const SUBTYPE_MARK_NAME = 'mark_name_leaf_control';

    /** (*COMMIT) */
    const SUBTYPE_COMMIT = 'commit_leaf_control';
    /** (*PRUNE) */
    const SUBTYPE_PRUNE = 'prune_leaf_control';
    /** (*SKIP) */
    const SUBTYPE_SKIP = 'skip_leaf_control';
    /** (*SKIP:NAME) */
    const SUBTYPE_SKIP_NAME = 'skip_name_leaf_control';
    /** (*THEN) */
    const SUBTYPE_THEN = 'then_leaf_control';

    /** (*CR) */
    const SUBTYPE_CR = 'cr_leaf_control';
    /** (*LF) */
    const SUBTYPE_LF = 'lf_leaf_control';
    /** (*CRLF) */
    const SUBTYPE_CRLF = 'crlf_leaf_control';
    /** (*ANYCRLF) */
    const SUBTYPE_ANYCRLF = 'anycrlf_leaf_control';
    /** (*ANY) */
    const SUBTYPE_ANY = 'any_leaf_control';

    /** (*BSR_ANYCRLF) */
    const SUBTYPE_BSR_ANYCRLF = 'bsr_anycrlf_leaf_control';
    /** (*BSR_UNICODE) */
    const SUBTYPE_BSR_UNICODE = 'bsr_unicode_leaf_control';

    /** (*NO_START_OPT) */
    const SUBTYPE_NO_START_OPT = 'no_start_opt_leaf_control';
    /** (*UTF8) */
    const SUBTYPE_UTF8 = 'utf8_leaf_control';
    /** (*UTF16) */
    const SUBTYPE_UTF16 = 'utf16_leaf_control';
    /** (*UCP) */
    const SUBTYPE_UCP = 'ucp_leaf_control';

    public $name;

    public function __construct($subtype = null, $name = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_CONTROL;
        $this->subtype = $subtype;
        $this->name = $name;
    }
    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        // Do nothing, the matching should be controlled by the matching engine.
    }
    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        // Do nothing, the matching should be controlled by the matching engine.
    }
    public function tohr() {
        return 'control';
    }
}

class qtype_preg_leaf_options extends qtype_preg_leaf {
    public $posopt;
    public $negopt;

    public function __construct($posopt = null, $negopt = null) {
        $this->type = qtype_preg_node::TYPE_LEAF_OPTIONS;
        $this->subtype = $this->type;
        $this->posopt = $posopt;
        $this->negopt = $negopt;
    }
    protected function match_inner($str, $pos, &$length, $matcherstateobj = null) {
        die ('TODO: implement abstract function match for qtype_preg_leaf_options class before use it!');
    }
    public function next_character($str, $pos, $length = 0, $matcherstateobj = null) {
        die ('TODO: implement abstract function character for qtype_preg_leaf_options class before use it!');
    }
    public function tohr() {
        $result = '(?';
        if (!empty($this->posopt)) {
            $result .= $this->posopt;
        }
        if (!empty($this->negopt)) {
            $result .= '-'.$this->negopt;
        }
        return $result.')';
    }
}

/**
 * Defines finite quantifiers with left and right borders, unary operator.
 * Possible errors: left border is greater than right one.
 */
class qtype_preg_node_finite_quant extends qtype_preg_operator {

    /** Is quantifier lazy? */
    public $lazy;
    /** Is quantifier greedy? */
    public $greedy;
    /** Is quantifier possessive? */
    public $possessive;
    /** Smallest possible repetition number. */
    public $leftborder;
    /** Biggest possible repetition number. */
    public $rightborder;

    public function __construct($leftborder = 0, $rightborder = 0, $lazy = false, $greedy = true, $possessive = false) {
        $this->type = qtype_preg_node::TYPE_NODE_FINITE_QUANT;
        $this->subtype = $this->type;
        $this->leftborder = $leftborder;
        $this->rightborder = $rightborder;
        $this->lazy = $lazy;
        $this->greedy = $greedy;
        $this->possessive = $possessive;
    }

    public function is_subpattern() {
        return true;    // Finite quantifier is a subpattern.
    }

    public function calculate_nflf(&$followpos) {
        parent::calculate_nflf($followpos);
        $this->nullable = $this->nullable || $this->leftborder == 0;
        // TODO - followpos for situations like {2,10}
    }

    public function lang_key($usedescription = false) {
        $result = parent::lang_key($usedescription);
        if ($usedescription) {
            if ($this->leftborder == 0) {
                $result .= '_0';
                if ($this->rightborder == 1) {
                    $result .= '1';
                }
            } else if ($this->leftborder == 1) {
                $result .= '_1';
            } else if ($this->leftborder == $this->rightborder) {
                $result .= '_strict';
            }
        }
        return $result;
    }

    public function lang_key_for_greediness() {
        if ($this->lazy) {
            return 'description_quant_lazy';
        }
        if ($this->possessive) {
            return 'description_quant_possessive';
        }
        return 'description_quant_greedy';
    }

    // TODO - ui_nodename().
}

/**
 * Defines infinite quantifiers node with the left border only, unary operator.
 */
class qtype_preg_node_infinite_quant extends qtype_preg_operator {

    /** Is quantifier lazy? */
    public $lazy;
    /** Is quantifier greedy? */
    public $greedy;
    /** Is quantifier possessive? */
    public $possessive;
    /** Smallest possible repetition number. */
    public $leftborder;

    public function __construct($leftborder = 0, $lazy = false, $greedy = true, $possessive = false) {
        $this->type = qtype_preg_node::TYPE_NODE_INFINITE_QUANT;
        $this->subtype = $this->type;
        $this->leftborder = $leftborder;
        $this->lazy = $lazy;
        $this->greedy = $greedy;
        $this->possessive = $possessive;
    }

    public function is_subpattern() {
        return true;    // Infinite quantifier is a subpattern.
    }

    public function calculate_nflf(&$followpos) {
        parent::calculate_nflf($followpos);
        $this->nullable = $this->nullable || $this->leftborder == 0;
        foreach ($this->lastpos as $lastpos) {
            if (!isset($followpos[$lastpos])) {
                $followpos[$lastpos] = array();
            }
            foreach ($this->operands[0]->firstpos as $firstpos) {
                if (!in_array($firstpos, $followpos[$lastpos])) {
                    $followpos[$lastpos][] = $firstpos;
                }
            }
        }
    }

    public function lang_key($usedescription = false) {
        $result = parent::lang_key($usedescription);
        if ($usedescription) {
            $result = 'description_' . $this->subtype;
            if ($this->leftborder == 0) {
                $result .= '_0';
            } else if ($this->leftborder == 1) {
                $result .= '_1';
            }
        }
        return $result;
    }

    public function lang_key_for_greediness() {
        if ($this->lazy) {
            return 'description_quant_lazy';
        }
        if ($this->possessive) {
            return 'description_quant_possessive';
        }
        return 'description_quant_greedy';
    }

    // TODO - ui_nodename().
}

/**
 * Defines concatenation, n-ary operator.
 */
class qtype_preg_node_concat extends qtype_preg_operator {

    public function __construct() {
        $this->type = qtype_preg_node::TYPE_NODE_CONCAT;
        $this->subtype = $this->type;
    }

    public function is_subpattern() {
        return false;    // Concatenation is not a subpattern.
    }

    public function calculate_nflf(&$followpos) {
        parent::calculate_nflf($followpos);
        $this->nullable = true;
        $this->firstpos = array();
        $this->lastpos = array();
        $count = count($this->operands);
        // Nullable and firstpos are calculated as always.
        for ($i = 0; $i < $count; $i++) {
            $operand = $this->operands[$i];
            if ($i == 0 || $this->nullable) {
                $this->firstpos = array_merge($this->firstpos, $operand->firstpos);
            }
            if (!$operand->nullable) {
                $this->nullable = false;
            }
        }
        // Lastpos is calculated backwards.
        for ($i = $count - 1; $i >= 0; $i--) {
            $operand = $this->operands[$i];
            $this->lastpos = array_merge($this->lastpos, $operand->lastpos);
            if (!$operand->nullable) {
                break;
            }
        }

        // Followpos is calculated for each operand except the last one.
        $followpos_prev = array(); // followpos calculated on the previous step.
        for ($i = $count - 2; $i >= 0; $i--) {
            $left = $this->operands[$i];
            $right = $this->operands[$i + 1];
            $followpos_new = array(); // followpos calculated on this step.

            foreach ($left->lastpos as $lastpos) {
                if (!isset($followpos[$lastpos])) {
                    $followpos[$lastpos] = array();
                }
                if (!isset($followpos_new[$lastpos])) {
                    $followpos_new[$lastpos] = array();
                }

                foreach ($right->firstpos as $firstpos) {
                    if (!in_array($firstpos, $followpos[$lastpos])) {
                        $followpos[$lastpos][] = $firstpos;
                        $followpos_new[$lastpos][] = $firstpos;
                    }
                }

                // Right operand is not nullable; continue.
                if (!$right->nullable || $i == $count - 2) {
                    continue;
                }

                // Right operand is nullable. Copy its follopos to current node.
                foreach ($followpos_prev as $from => $to) {
                    if (!isset($followpos[$from])) {
                        $followpos[$from] = array();
                    }
                    foreach ($to as $tmp) {
                        if (!in_array($tmp, $followpos[$lastpos])) {
                            $followpos[$lastpos][] = $tmp;
                            $followpos_new[$lastpos][] = $tmp;
                        }
                    }
                }
            }
            $followpos_prev = $followpos_new;
        }
    }
}

/**
 * Defines alternation, n-ary operator.
 */
class qtype_preg_node_alt extends qtype_preg_operator {

    public function __construct() {
        $this->type = qtype_preg_node::TYPE_NODE_ALT;
        $this->subtype = $this->type;
    }

    public function is_subpattern() {
        return false;    // Alternation is not a subpattern.
    }

    public function calculate_nflf(&$followpos) {
        parent::calculate_nflf($followpos);
        $this->nullable = false;
        $this->firstpos = array();
        $this->lastpos = array();
        for ($i = 0; $i < count($this->operands); $i++) {
            $operand = $this->operands[$i];
            if ($operand->nullable) {
                $this->nullable = true;
            }
            $this->firstpos = array_merge($this->firstpos, $operand->firstpos);
            $this->lastpos = array_merge($this->lastpos, $operand->lastpos);
        }
    }
}

/**
 * Defines lookaround assertions, unary operator.
 */
class qtype_preg_node_assert extends qtype_preg_operator {

    /** Positive lookahead assert. */
    const SUBTYPE_PLA = 'pla_node_assert';
    /** Negative lookahead assert. */
    const SUBTYPE_NLA = 'nla_node_assert';
    /** Positive lookbehind assert. */
    const SUBTYPE_PLB = 'plb_node_assert';
    /** Negative lookbehind assert. */
    const SUBTYPE_NLB = 'nlb_node_assert';

    public function __construct($subtype = null) {
        $this->type = qtype_preg_node::TYPE_NODE_ASSERT;
        $this->subtype = $subtype;
    }

    public function tohr() {
        return 'node assert';
    }

    public function is_subpattern() {
        return true;    // Lookaround assertion is a subpattern.
    }

    public function calculate_nflf(&$followpos) {
        // parent::calculate_nflf($followpos);
        $this->nullable = false;
        $this->firstpos = array($this->id);
        $this->lastpos = array($this->id);
    }

    // TODO - ui_nodename().
}

/**
 * Defines subexpressions (yes, NOT a subpattern), unary operator.
 */
class qtype_preg_node_subexpr extends qtype_preg_operator {

    /** Subexpression. */
    const SUBTYPE_SUBEXPR = 'subexpr_node_subexpr';
    /** Once-only subexpression. */
    const SUBTYPE_ONCEONLY = 'onceonly_node_subexpr';
    /** Grouping node. For author's tools only.*/
    const SUBTYPE_GROUPING = 'grouping_node_subexpr';
    /** Duplicate subexpressions. For authoring tools only.*/
    const SUBTYPE_DUPLICATE_SUBEXPRESSIONS = 'duplicate_node_subexpr';

    /** Subexpression number. */
    public $number = -1;
    /** Subexpression name. */
    public $name = null;

    public function __construct($subtype, $number = -1, $name = null) {
        $this->type = qtype_preg_node::TYPE_NODE_SUBEXPR;
        $this->subtype = $subtype;
        $this->number = $number;
        $this->name = $name;
    }

    public function is_subpattern() {
        return true;    // Subexpression is a subpattern.
    }

    public function lang_key($usedescription = false) {
        $result = parent::lang_key($usedescription);
        if ($usedescription && $this->name !== null) {
            $result .= '_name';
        }
        return $result;
    }

    // TODO - ui_nodename().
}

/**
 * Defines conditional subexpressions, unary, binary or ternary operator.
 * The first operand yes-pattern, second - no-pattern, third - the lookaround assertion (if any).
 * Possible errors: there is no backreference with such number in expression
 */
class qtype_preg_node_cond_subexpr extends qtype_preg_operator {

    /** Absolute/relative/named references to subexpressions. */
    const SUBTYPE_SUBEXPR = 'subexpr_node_cond_subexpr';
    /** Recursion condition. */
    const SUBTYPE_RECURSION = 'recursion_node_cond_subexpr';
    /** Define subexpression for reference. */
    const SUBTYPE_DEFINE = 'define_node_cond_subexpr';
    /** Positive lookahead assert. */
    const SUBTYPE_PLA = 'pla_node_cond_subexpr';
    /** Negative lookahead assert. */
    const SUBTYPE_NLA = 'nla_node_cond_subexpr';
    /** Positive lookbehind assert. */
    const SUBTYPE_PLB = 'plb_node_cond_subexpr';
    /** Negative lookbehind assert. */
    const SUBTYPE_NLB = 'nlb_node_cond_subexpr';

    /** Subexpression number. */
    public $number = -1;

    public function __construct($subtype = null, $number = -1, $condbranch = null) {
        $this->type = qtype_preg_node::TYPE_NODE_COND_SUBEXPR;
        $this->subtype = $subtype;
        $this->number = $number;
        $this->operands = $condbranch === null ? array() : array($condbranch);   // Assertion condition is the first operand.
    }

    public function is_condition_assertion() {
        return $this->subtype == self::SUBTYPE_PLA || $this->subtype == self::SUBTYPE_NLA || $this->subtype == self::SUBTYPE_PLB || $this->subtype == self::SUBTYPE_NLB;
    }

    public function is_subpattern() {
        return true;    // Conditional subexpression is a subpattern.
    }

    public function calculate_nflf(&$followpos) {
        parent::calculate_nflf($followpos);
        // TODO what should be here?
    }

    public function lang_key($usedescription = false) {
        if (!$usedescription) {
            return parent::lang_key($usedescription);
        }
        $result = $this->is_condition_assertion()
            ? 'description_' . $this->type
            : 'description_' . $this->subtype;

        if ($this->number === 0) {
            $result .= '_all';
        } else if (is_string($this->number)) {
            $result .= '_name';
        }
        return $result;
    }

    // TODO - ui_nodename().
}

/**
 * Defines error nodes, used when syntax errors in the regular expression occur.
 */
class qtype_preg_node_error extends qtype_preg_operator {

    const SUBTYPE_UNKNOWN_ERROR                = 'unknown_error_node_error';                  // Unknown parse error.
    const SUBTYPE_MISSING_OPEN_PAREN           = 'missing_open_paren_node_error';             // Closing paren without opening  xxx).
    const SUBTYPE_MISSING_CLOSE_PAREN          = 'missing_close_paren_node_error';            // Opening paren without closing  (xxx.
    const SUBTYPE_MISSING_COMMENT_ENDING       = 'missing_comment_ending_node_error';         // Missing ) after comment.
    const SUBTYPE_MISSING_CONDSUBEXPR_ENDING   = 'missing_condsubexpr_ending_node_error';     // Missing conditional subexpression name ending.
    const SUBTYPE_MISSING_CALLOUT_ENDING       = 'missing_callout_ending_node_error';         // Missing ) after (?C.
    const SUBTYPE_MISSING_CONTROL_ENDING       = 'missing_control_ending_node_error';         // Missing ) after control sequence.
    const SUBTYPE_MISSING_SUBEXPR_NAME_ENDING  = 'missing_subexpr_name_ending_node_error';    // Missing subexpression name ending.
    const SUBTYPE_MISSING_BRACKETS_FOR_G       = 'missing_brackets_for_g_node_error';         // \g is not followed by {}, <>, or ''.
    const SUBTYPE_MISSING_BRACKETS_FOR_K       = 'missing_brackets_for_k_node_error';         // \k is not followed by {}, <>, or ''.
    const SUBTYPE_UNCLOSED_CHARSET             = 'unclosed_charset_node_error';               // Unclosed brackets in a character set.
    const SUBTYPE_POSIX_CLASS_OUTSIDE_CHARSET  = 'posix_class_outside_charset_node_error';    // POSIX class ouside of a character set.
    const SUBTYPE_QUANTIFIER_WITHOUT_PARAMETER = 'quantifier_without_parameter_node_error';   // Quantifier at the start of the expression. NOTE: currently incompatible with PCRE which treats it as a character.
    const SUBTYPE_INCORRECT_QUANT_RANGE        = 'incorrect_quant_range_node_error';          // Incorrect quantifier ranges: {5,3}.
    const SUBTYPE_INCORRECT_CHARSET_RANGE      = 'incorrect_charset_range_node_error';        // Incorrect character set range: [z-a].
    const SUBTYPE_SET_UNSET_MODIFIER           = 'set_unset_same_modifier_node_error';        // Set and unset same modifier at ther same time.
    const SUBTYPE_UNSUPPORTED_MODIFIER         = 'unsupported_modifier_node_error';           // Unsupported modifier.
    const SUBTYPE_UNKNOWN_UNICODE_PROPERTY     = 'unknown_unicode_property_node_error';       // Unknown unicode property.
    const SUBTYPE_UNKNOWN_POSIX_CLASS          = 'unknown_posix_class_node_error';            // Unknown posix class.
    const SUBTYPE_UNKNOWN_CONTROL_SEQUENCE     = 'unknown_control_sequence_node_error';       // Unknown control sequence (*...).
    const SUBTYPE_CONDSUBEXPR_TOO_MUCH_ALTER   = 'condsubexpr_too_much_alter_node_error';     // Too much top-level alternations in a conditional subexpression.
    const SUBTYPE_CONDSUBEXPR_ASSERT_EXPECTED  = 'condsubexpr_assert_expected_node_error';    // Assertion or condition expected.
    const SUBTYPE_CONSUBEXPR_ZERO_CONDITION    = 'condsubexpr_zero_condition_node_error';     // Invalid condition (?(0).
    const SUBTYPE_SLASH_AT_END_OF_PATTERN      = 'slash_at_end_of_pattern_node_error';        // \ at end of pattern.
    const SUBTYPE_C_AT_END_OF_PATTERN          = 'c_at_end_of_pattern_node_error';            // \c at end of pattern.
    const SUBTYPE_CX_SHOULD_BE_ASCII           = 'cx_should_be_ascii_node_error';             // \c should be followed by an ascii character.
    const SUBTYPE_UNEXISTING_SUBEXPR           = 'unexisting_subexpr_node_error';             // Reference to unexisting subexpression.
    const SUBTYPE_DUPLICATE_SUBEXPR_NAMES      = 'duplicate_subexpr_names_node_error';        // Two named subexpressions have the same name.
    const SUBTYPE_DIFFERENT_SUBEXPR_NAMES      = 'different_subexpr_names_node_error';        // Different subexpression names for subexpressions of the same number.
    const SUBTYPE_SUBEXPR_NAME_EXPECTED        = 'subexpr_name_expected_node_error';          // Subexpression name expected.
    const SUBTYPE_UNRECOGNIZED_PQH             = 'unrecognized_pqh_node_error';               // Unrecognized character after (? or (?-.
    const SUBTYPE_UNRECOGNIZED_PQLT            = 'unrecognized_pqlt_node_error';              // Unrecognized character after (?<.
    const SUBTYPE_UNRECOGNIZED_PQP             = 'unrecognized_pqp_node_error';               // Unrecognized character after (?P.
    const SUBTYPE_CHAR_CODE_TOO_BIG            = 'char_code_too_big_node_error';              // Character code too big.
    const SUBTYPE_CHAR_CODE_DISALLOWED         = 'char_code_disallowed_node_error';           // Character code disallowed.
    const SUBTYPE_CALLOUT_BIG_NUMBER           = 'callout_big_number_node_error';             // Too big number in (?C...).
    const SUBTYPE_LNU_UNSUPPORTED              = 'lnu_unsupported_node_error';                // \L, \l, \N{name}, \U, and \u are unsupported.

    /** Additional info, should be a string. */
    public $addinfo;

    public function __construct($subtype = null, $addinfo = null) {
        $this->type = qtype_preg_node::TYPE_NODE_ERROR;
        $this->subtype = $subtype;
        $this->addinfo = $addinfo;
    }

    public function is_subpattern() {
        return false;    // Of course it's not.
    }

    /**
     * Returns a user interface error string for the error, represented by this node.
     */
    public function error_string() {
        $a = new stdClass;
        $a->linefirst = $this->position->linefirst;
        $a->linelast = $this->position->linelast;
        $a->colfirst = $this->position->colfirst;
        $a->collast = $this->position->collast;
        $a->addinfo = $this->addinfo;
        return get_string($this->subtype, 'qtype_preg', $a);
    }
}
